#pragma comment(linker, "/STACK:10000000")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <cstdio>
#include <cassert>
#include <string>
#include <cstring>
#define ldb long double
#define ll long long
#define fi first
#define se second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define fill(a, c) memset(a, c, sizeof(a))
#define sqr(a) ((a) * (a))
#define nextLine() {int c = 0; while((c = getchar()) != 10 && c != EOF);}
#define getBit(mask, k) (((mask) / pw[k]) % pw[1])
#define setBit(mask, k, l) (((mask) / pw[k + 1] * pw[1] + (l)) * pw[k] + ((mask) % pw[k]))
#define debug(a) cerr << #a << " = " << (a) << " ";
#define debugl(a) cerr << #a << " = " << (a) << "\n";
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define ff first
#define ss second 
const ldb eps = 1e-9;
const int inf = 1 << 28;
const ldb pi = fabsl(atan2l(0.0, -1.0));
using namespace std;


ll P, L, R;
int M;
bool good[10];
int u[12];
int checked[1000001];

#define MAXP 100000

void load()
{
	cin >> M >> P >> L >> R;
	for (int i = 0; i < M; i++)
	{
		scanf("%d", &u[i]);
		good[u[i]] = true;
	}
	sort(u, u + M);
}


inline bool check_digits(int x)
{
	while (x)
	{
		if (!good[x % 10]) return false;
		x /= 10;
	}
	return true;
}

void solve_dull()
{
	/*
	ll res = 0;
	for (ll i = L; i <= R; i++)
	{
		ll x = i;
		while (x)
		{
			if (!good[x % 10ll]) break;
			x /= 10ll;
		}
		if (x == 0) res++;
	}
	cout << res;
	return;
	*/

	for (int i = 0; i <= 1000000; i++)
	{
	//	cerr << i << "\n";
		checked[i] = check_digits(i);
		//if (checked[i])
		//	cerr << i << "\n";
	}
	ll first;
	if (L % P == 0) first = L;
	else first = L + P - (L % P);
	
	int fst_part, sec_part;
	
	int non_zero = u[0];
	if (M > 1 && non_zero == 0) non_zero = u[1];


	ll res = 0;
	for (; first <= R; first += P)
	{
		fst_part = first / 1000000ll;
		sec_part = first % 1000000ll;
		if (first > 100000 && sec_part < 100000) sec_part += non_zero * 100000;
		if (checked[fst_part] && checked[sec_part])
			res++;
	}
	cout << res;
}


int sz;
int a[123];
ll dp[13][100000][3];

ll f(int i, int r, int l)
{
	if (i == 0)
		return r == 0 && l != 2;
	if (dp[i][r][l] != -1) return dp[i][r][l];
	dp[i][r][l] = 0;
	if (i != sz && r == 0)
		dp[i][r][l]++;
	int j = 0;
	if (i == sz && u[0] == 0)
		j++;
	int nl, nr;
	for (; j < M; j++)
	{
		nl = l;
		if (l == 0 && u[j] < a[i - 1]) nl = 1;
		if (l == 0 && u[j] > a[i - 1]) nl = 2;
		nr = (r * 10 + u[j]) % P;
		dp[i][r][l] += f(i - 1, nr, nl);
	}
//	cerr << i << " " << r << " " << l << ":" << dp[i][r][l] << "\n";
	return dp[i][r][l];
}

ll count(ll N)
{
	if (N == 0) return 0;
	sz = 0;
	while (N)
	{
		a[sz++] = N % 10;
		N /= 10;
	}
//	for (int i = sz - 1; i >= 0; i--)
//		cerr << a[i];
//		cerr << "\n";
	memset(dp, -1, sizeof dp);
	return f(sz, 0, 0);
}

void solve()
{
	if (P > MAXP)
	{
		solve_dull();
	}
	else
	{
		cout << count(R) - count(L - 1);
	}
}

#define file "np"
int main()
{
	freopen(file".in", "rt", stdin);
	freopen(file".out", "wt", stdout);
	load();
	solve();
	return 0;
}
